The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for access control lists (ACLs) and forwarding decisions is a demanding part of switch and router design. This packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs require matching packets on a subset of fields of the packet flow label, with the semantics of a sequential search through the ACL rules. IP forwarding requires a longest prefix match.
One known approach uses binary and/or ternary content-addressable memories to perform packet classification. Ternary content-addressable memories allow the use of wildcards in performing their matching, and thus are more flexible than binary content-addressable memories. These content-addressable memories are expensive in terms of power consumption and space, and are limited in the size of an input word (e.g., 72, 144, 288 bits, etc.) on which a lookup operation is performed as well as the number of entries which can be matched.
Various applications that use packet classification, such as Security Access Control, Quality of Service etc., typically need to match source and/or destination addresses. These addresses can be quite large, and possibly too large for providing all bits representing one or more addresses to a content-addressable memory. For example, Internet Protocol version 6 (IPv6) uses addresses having a length of 128 bits and a typical large content-addressable memory has a maximum search width of 288 bits. Therefore, almost all the bits of a content-addressable memory would be used for matching the source and destination addresses, while providing a small, and quite possibly insufficient number of input bits for matching other criteria such as source and destination port numbers, protocol and other header fields, etc. Needed are new methods and apparatus for performing lookup operations, especially for IPv6 and other addresses, using content-addressable memories and other devices.